package com.lqian.simplestructure.sorted;

import java.util.Arrays;

/**
 * 快速排序
 * D&C 分治思想
 * 基准值 (pivot)
 * 找到比基准值小以及比基准值大的元素
 * 将数组分成两个子数组：小于基准值的元素以及大于基准值的元素
 * 递归调用快速排序
 */
public class QuickSort {

    public static void main(String[] args) {
        int [] arr = new int[] {3,4,6,7,2,7,2,8,0,9,1};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr,int start,int end){
        if (start < end) {
        //基准值，假设为第一个元素
         int pivot =arr[start];
         //记录需要排序的下标
         int low = start;
         int high = end;
         //循环比较找比基准值大的和小的

            while (low < high) {
                //右边大于基准值的
                while (low < high && pivot <= arr[high]) {
                    high--;
                }
                //使右边的数字替换左边的数
                //while条件不成立，右边的大于左边
                arr[low] = arr[high];
                //左边边大于基准值的
                while (low < high && arr[low] <= pivot) {
                    low++;
                }
                //使左边的数字替换右边的数
                //while条件不成立，左边的大于右边
                arr[high] = arr[low];
            }
            //重新赋基准值
            arr[low] = pivot;
            quickSort(arr,start,low);
            quickSort(arr,low+1,end);

        }

    }
}
